package com.study.algorithm.linkedList;

import java.util.Deque;
import java.util.LinkedList;

public class RemoveNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 创建虚拟头节点，简化头节点删除操作
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 2. 初始化快慢指针
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 3. 快指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 4. 同步移动快慢指针，直到快指针到达末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 5. 删除倒数第n个节点（slow.next指向目标节点）
        slow.next = slow.next.next;

        // 6. 返回新链表的头节点
        return dummy.next;
    }
    public ListNode removeNthFromEnd1(ListNode head, int n) {

        //计算长度方法

        //初始化虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        int length = getLength(head);

        //定位到要删除的前驱节点
        ListNode current = dummy;
        for (int i = 0; i < length - n; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;

    }

    private int getLength(ListNode head) {
        int length = 0;
        //遍历链表直到空
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {

        //栈实现方法


        //初始化虚拟头节点
        ListNode dummy = new ListNode(-1);

        dummy.next = head;//让虚拟头节点执行头节点

        //采用栈来存储所以节点
        Deque<ListNode> stack = new LinkedList<>();
        ListNode current = dummy;
        //遍历把所有节点压入栈中
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        //第二次遍历：弹出n个节点
        // 这样栈顶就是倒数第n+1个节点（要删除节点的前驱）
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        // 此时栈顶元素就是要删除节点的前驱节点
        ListNode predecessor = stack.peek();
        // 删除目标节点：跳过倒数第n个节点
        predecessor.next = predecessor.next.next;

        return dummy.next;
    }

}
